0. Antecendentes

Imagina que tienes una escala de 8h en una ciudad desconocida, una tarde libre tras un viaje de trabajo o simplemente no tienes plan para un domingo. ¿Cómo planificar una ruta sin perder tiempo y esfuerzo?.De esta necesidad surge la idea de crear una aplicación que crea diferentes itinerarios en función de las necesidades de cada usuario y tiempo disponible.

1. Objetivo

El objetivo del trabajo es establecer una interfaz que muestre rutas personalizadas a los usuarios en base a:

2. Datos

2.1. Obetención de Datos

En un primer intento se obtuvieron los datos de distintos puntos de interés de Madrid a partir de la API de Google Places.

Dado que una gran parte de los resultados obtenidos provenían de ‘places’ autoeditados por los usuarios y no se disponía del número de reviews de cada lugar para poder evaluar si el lugar era realmente importante o no, se decidió hacer web-scraping de www.tripadvisor.com

En este caso, se ha optado hacerlo únicamente para Madrid para simplificar, pero se podría replicar para más ciudades con relativa facilidad.

De aquí obtuvimos las referencias de 767 puntos de interés asociados a Madrid y más de 2.600 restaurantes de la misma ciudad.

Ver 00.WebScraping.R

La información disponible era:

Muestra información obtenida de los puntos de interés
nombre tipo opiniones rank
Museo del Prado Museos especializados 49563 2
Parque del Retiro Edificios con valor arquitectónico 47398 1
Palacio Real de Madrid Edificios con valor arquitectónico 29948 5
Mercado San Miguel Mercadillos 26483 10
Plaza Mayor Edificios con valor arquitectónico 22294 9
Muestra información obtenida de los restaurantes
nombre opiniones rank precio estilo
11529 Centro asturiano de Madrid 11 3739
17482 Hermanos Arananz 1 7946
2425 RESTAURANTE 29 FANEGAS 238 487 €€ - €€€ Mediterránea
10053 La imprenta 136 2907 €€ - €€€ Española
12996 Cocina Asiatica Go 24 4636 €€ - €€€ Asiática

2.2. Limpieza y Enriquecimiento

Tanto para los puntos de interés como para los restaurantes se exigió que tuvieran un mínimo de 100 reviews para poder contar con información robusta, y para los restaurantes que además contaran con una valoracíon económica (precio medio) del mismo.

Con esto redujimos los puntos de interés a 158 y los restaurantes a 2.000

Para poder ubicar todos estos puntos, calcular distancias y tiempos entre ellos, se recurrió a la API de GoogleMaps, a partir de la cual se obtuvieron sus coordenadas latitud y longitud. Además de otras características como el rating, dirección,…

Muestra de la información final sobre Puntos de Interés
nombre lat lon tipo Agrupacion opiniones rating
121 San Sebastian de los Reyes The Style Outlets 40.56720 -3.608502 Centros comerciales Compras 155 4.200000
15 Palacio de Cibeles 40.41888 -3.691785 Edificios con valor arquitectónico Monumentos y Edificios 4599 4.360145
11 Puerta del Sol 40.41695 -3.703529 Puntos emblemáticos y de interés Puntos emblematicos 9450 4.500000
87 Museo del Aire 40.36496 -3.804246 Museos militares Museos 293 4.600000
101 Puerta de Europa - Torres KIO 40.46670 -3.688649 Puntos emblemáticos y de interés Puntos emblematicos 236 4.300000
Muestra de la información final sobre restaurantes
nombre formatted_address lat lon opiniones rank precio rating
771 El Restaurante Vegetariano Calle de Angosta de los Mancebos, 6, 28005 Madrid, Spain 40.41287 -3.713466 126 985 2 4.6
1810 Ondinas Do Mendo Calle de Villaamil, 4, 28039 Madrid, Spain 40.45684 -3.705080 232 310 1 4.4
983 Ginos Paseo de la Castellana, 278, 28046 Madrid, Spain 40.47534 -3.686132 186 2311 2 3.8
679 El Jardin de Orfila por Mario Sandoval Calle de Orfila, 6, 28010 Madrid, Spain 40.42732 -3.693211 260 345 3 4.4
2444 The Good Burger nº, Av. del Monasterio de El Escorial, 30, 28049 Madrid, Spain 40.50420 -3.704395 193 3414 1 4.0

Ver 01.Working_with_Data.R

2.3. Datos de entrada (elección del usuario)

  • Fijamos el punto de inicio y fin de la ruta:

    • El punto de inicio y fin podrá ser el mismo o no
    • Forzaremos a que siempre lleve la palabra “Madrid” detrás para descartar ambigüedades de localizaciones. Por ejemplo si meto solo “Puerta del Sol”,me devolverá las coordenadas de Irvine, USA

  • Fijamos las horas de inicio y fin de la ruta:

    • Si en el tiempo que queremos hacer la ruta, coincide con la hora de la comida, buscaremos un restaurante cercano y meteremos una parada para comer

  • Fijamos el tipo de transporte:

    • Podemos elegir entre hace la ruta andando si queremos ir dando un paseo o en coche si tenemos que recorrer largas distancias (por ejemplo si venimos desde el Aeropuerto)

  • Elegimos la tipología de lugares a visitar y el rango de puntuación de los mismos:

    • Podemos elegir entre:

  • También podemos elegir qué tipo de comida queremos, puntuación y rango de precios:

    • Podemos elegir entre:

Resumen de la elección (Ejemplo):

Ejemplo de elección del usuario
Ejemplo
Punto Inicio: Puerta del Sol, Madrid , Punto Final: Plaza de Colon, Madrid
Hora Inicio: 8 , Hora Final: 17
Modo de Transporte: caminando
Tipo de lugares a visitar: Museos con una puntuación entre: 4 y 5
Tipo de comida: Española con una puntuación entre: 4.5 y 5, y un precio (1 a 3) de: 2

3. Modelos de estimación de tiempos

Dado que tenemos unos 2.200 puntos entre lugares de interés y restaurantes, si quisiéramos obtener todas las distancias entre los puntos necesitaríamos una matriz con casi 5millones de combinaciones. Trabajar con un matriz de distancias haría que el proceso de cálculo fuera lento y nos obligaríamos a relizar un número muy elevado de consultas a la API de Google Maps con su correspondiente coste.

Para ello, vamos a crear dos modelos de estimación de tiempos en base a las distancias calculadas con la Fórmula de Haversine https://en.wikipedia.org/wiki/Haversine_formula y distancias en tiempo obtenidos mediante la API de Google Maps. Para esto, cogemos 1.000 puntos aletorios de Madrid, y los agrupamos en pares de puntos (500 pares),calculando las distancias y los tiempos para estos 500 ‘trayectos’.

Con estas 500 combianciones y mediante regresiones lm(), creamos los modelos de estimación de tiempos.

Modelo caminando: podemos estimar el tiempo que hay caminando entre dos puntos, a partir de sus coordenadas.

Dado que los tiempos en coche dependen de muchos más factores que si lo hiciéramos andando incluimo además para el modelo más variables como la franja horaria y tipo de trayecto.

Modelo en coche: podemos estimar el tiempo el tiempo en coche entre dos puntos, a partir de sus coordenadas, de la franja horaria (simplificada en mañana y tarde) y si de trata de un desplazamiento dentro de la M30, fuera o mixto.

Ver 02.Estimation_Models.R

4. Matrices de tiempos

Una vez que tenemos los modelos de estimación podemos calcular los tiempos entre todos los puntos que tenemos.

Filtro de los lugares y matrices de tiempos

Dado que trabajar con matrices de tiempos puede resultar algo lento si se trabaja con todas las posibles combinaciones, filtramos de antemano las selecciones que haya hecho el usuario, reduciendo la cantidad de combinaciones posibles y el tiempo de cálculo.

Cálculo de distancias del origen y final a todos los posibles puntos

Para ello utilizo creamos una función que calcula las ditancias entre las coordenadas del punto inicial y final de la ruta que hemos planteado respecto a las coordenadas de todos los puntos de interés.

A continuación transfomamos estas distancias en tiempos, a partir de los modelos que ya hemos creado en el punto 3. Modelos de estimación de tiempos.

Ver 03.Functions.R

5. Cálculo de la Ruta Óptima

5.1 Criterio de selección de Lugares

A la hora de crear la ruta, tendremos en cuenta otros factores como: * Distancia a los puntos. Aprovechar los puntos que estén más cerca para evitar grandes desplazamientos (sobretodo si el desplazamiento es a pie) * El rating otorgado por los visitantes, dando mayor importancia a los mejor valorados. * El número de opiniones sobre el lugar, dando mayor importancia a los que hayan tenido más reviews.

Para esto ponderaremos estos 3 factores para crear un único factor de importancia.

Ver 04.Algorithm.R

5.2 Algoritmo para el cálculo de la ruta Óptima

El problema al que nos enfrentamos es un problema clásico de la Estadística.

Se trata del problema del Vendedor Viajante (Travel Salesman Problem) * Travel Salesman Problem (Wikipedia)(https://en.wikipedia.org/wiki/Travelling_salesman_problem) * Paquete TSP para R(https://cran.r-project.org/package=TSP/TSP.pdf)

5.3 Preparo los datos para aplicar el Algoritmo TSP

El tiempo disponible para realizar la ruta será la diferencia entre la hora final y la inicial, menos el tiempo que dediquemos a comer (si aplica)

Ahora reordenamos las matrices de tiempos teniendo en cuenta la importancia de los puntos de interés, según los criterios del punto 5.1.

5.3.1 Calculamos la ruta óptima

Para eso, partimos de la ruta más sencilla posibles que es ir del punto inicial al final, observamos el tiempo necesario para ir de un punto al otro y vemos si está dentro de nuestro tiempo disponible (Ver punto 5.3)

Creamos una función que va añadiendo puntos uno a uno en función de la importancia de los puntos y aplicamos el TSP, agregando los tiempos necesarios para recorrer la ruta y evaluando si está dentro de nuestro tiempo disponible. Esto se repite hasta que encuentre la ruta que más se ajusta al tiempo y el orden óptimo de para recorrerla.

Ver 04.Algorithm.R

5.3.2 Ponemos un orden a la ruta

Ordenamos la ruta con lo que nos devuelve el TSP.

En verde el punto inicial en rojo el el final
X lat lon nombre tipo rating opiniones tiempoNecesario
1 40.42512 -3.690241 Plaza de Colón, Madrid, Spain Fin – – 0
2 40.41604 -3.694925 Museo Nacional Thyssen-Bornemisza Museos especializados 4.6 14587 120
11 40.41378 -3.692127 Museo del Prado Museos especializados 4.7 49563 120
3 40.40791 -3.694557 Museo Nacional Centro de Arte Reina Sofía Museos de arte 4.5 14202 120
5 40.41695 -3.703529 Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain Inicio – – 0

5.3.3 Agregamos los tiempos a destino

Añadimos el tiempo que se tarda en llegar desde cada punto al siguiente, teniendo en cuenta el tiempo que pasaremos en cada punto.

Esto se definió en función de la tipología del sitio. Por ejemplo: aproximadamente 2 horas para ver los museos.

X lat lon nombre tiempoNecesario tiempoCoche tiempoCaminando id
5 40.41695 -3.703529 Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain 0 NA NA 5
3 40.40791 -3.694557 Museo Nacional Centro de Arte Reina Sofía 120 11 20 4
11 40.41378 -3.692127 Museo del Prado 120 11 9 3
2 40.41604 -3.694925 Museo Nacional Thyssen-Bornemisza 120 10 5 2
1 40.42512 -3.690241 Plaza de Colón, Madrid, Spain 0 11 17 1

5.3.4 Agregamos lógica de restaurantes

Después de acumular los tiempos, se calcula entre qué dos puntos habría que hacer una parada para comer, estimada en el entorno de las 14:30.

Para simplificar las combinaciones, nos quedamos con los restaurantes que cumplen con la selección del usuario, y se prioriza en función de la distancia al punto anterior y siguiente.

Para elegir el restaurante, creamos una función con la que nos quedamos con los restaurantes que están a una distancia similar a la distancia que hay al siguiente punto + un retraso (por si no hay ninguno cerca y tenemos que alejarnos). Si no encontramos nada a esa distancia, vamos aumentando el retraso 1min hasta un máximo de 30min, para poder encontrar un sitio. Si aún así no hay ninguno, no habrá parada para comer.

Restaurante elegido según criterios y algoritmo:
X lat lon name rating opiniones precio Espanola distLugCami criterio
1 40.41254 -3.695427 Moratin 4.7 115 2 1 10.39776 7.553838

5.3.5 Añadimos el restaurante a la ruta

En amarillo hemos incluido el restaurante en la ruta
X.1 X lat lon nombre tiempoNecesario tiempoCoche tiempoCaminando id
1 5 40.41695 -3.703529 Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain 0 NA NA 5
2 3 40.40791 -3.694557 Museo Nacional Centro de Arte Reina Sofía 120 11 20 4
3 11 40.41378 -3.692127 Museo del Prado 120 11 9 3
4 1 40.41254 -3.695427 Moratín 60 NA 10 6
41 2 40.41604 -3.694925 Museo Nacional Thyssen-Bornemisza 120 10 5 2
5 1 40.42512 -3.690241 Plaza de Colón, Madrid, Spain 0 11 17 1

6. Ouput Final

El resultado final es un archivo html, que te muestra la selección, la ruta con las paradas y un detalle de las mismas si nos colocamos encima del ‘pin’.

7. ShinyApp

El resultado final es un ShinyApp donde el usuario puede crear su propia ruta en base a sus preferencias

https://mdomingosancho.shinyapps.io/AppMyStopover

Ver 05.MyStopOverApp.R